package com.lw.leetcode.back.b;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * 面试题 08.07. 无重复字符串的排列组合
 *
 * @author liw
 * @version 1.0
 * @date 2022/1/11 20:39
 */
public class Permutation2 {

    public static void main(String[] args) {
        Permutation2 test = new Permutation2();
        String str = "abc";
        String[] permutation = test.permutation(str);
        System.out.println(Arrays.toString(permutation));

    }

    private int length;
    private char[] chars;
    private List<String> list;

    public String[] permutation(String str) {
        this.list = new ArrayList<>();
        this.chars = str.toCharArray();
        this.length = chars.length;
        char[] arr = new char[length];
        find(0, arr);
        String[] strs = new String[list.size()];
        int i = 0;
        for (String s : list) {
            strs[i++] = s;
        }
        return strs;
    }

    private void find(int index, char[] arr) {
        if (index == length) {
            list.add(new String(arr));
            return;
        }
        for (int i = 0; i < length; i++) {
            char c = chars[i];
            if (c == '*') {
                continue;
            }
            arr[index] = c;
            chars[i] = '*';
            find(index + 1, arr);
            chars[i] = c;
        }
    }

}
